In a data processing system, if more than one process requires access to shared data, a synchronization mechanism is used to coordinate access to the shared data among the different processes. The synchronization mechanism is necessary to prevent one process from modifying the shared data before another process has finished working with the shared data. Synchronization of shared data becomes more complex if the multiple processes run on physically distinct processors in a multiprocessor system that accesses the shared data from a shared memory.
In general, to achieve synchronization of shared data, lock variables, known as semaphores, are used to coordinate access to the shared data among processes. A semaphore is a flag stored in shared memory that is accessible by the processes. If a process accesses and locks a semaphore associated with a segment of shared data, no other process is allowed to access that segment of shared data.
More specifically, a process reads a semaphore associated with a particular segment of shared data to test semaphore state. If the semaphore contains a value of ‘0’, associated shared data is free, and if the semaphore contains a value of ‘1’, associated shared data is locked. The process keeps reading and testing the state of the semaphore until the value of the semaphore indicates that the lock on the associated segment of shared data is free. This continuous reading and testing of the semaphore is known as spin-waiting. If the semaphore indicates the lock is free, the process then races against other processes that were similarly spin-waiting to lock the associated segment of shared data.
Conventionally, a processor uses an atomic swap instruction that both reads semaphore value and stores a ‘1’ into the semaphore to lock an associated segment of shared data in a single step. The process that wins access to the shared data will read a ‘0’ from the semaphore, while the losing process(es) will read a ‘1’ from the semaphore. The winning process then uses the shared data and stores a ‘0’ into the associated semaphore when finished with the shared data.
Some processors, however, do not support atomic read-modify-write or atomic swap operations. In a data processing system having more than one of such processors where each may execute more than one process, semaphores stored in a shared memory are conventionally not sufficient to be used to reliably control access to shared data within the shared memory.
Accordingly, it would be both desirable and useful to provide method and apparatus for synchronization of a shared memory in a multiprocessor system that overcomes one or more above-described limitations associated with semaphores stored in shared memory.